#pragma once

#include <stack>
#include <utility>
#include <vector>

namespace solution_084
{

class Solution
{
public:
    int largestRectangleArea(std::vector<int>& heights)
    {
        heights.push_back(-1);
        int max_area = 0;

        std::stack<int> mono;
        mono.push(-1);
        for (int i = 0; i < (int)heights.size(); ++i) {
            while (mono.top() >= 0 && heights.at(i) <= heights.at(mono.top())) {
                int bar = heights.at(mono.top());
                mono.pop();
                max_area = std::max(max_area, bar * (i - mono.top() - 1));
            }
            mono.push(i);
        }

        return max_area;
    }

    int largestRectangleAreaBF(std::vector<int>& heights)
    {
        if (heights.empty())
            return 0;

        int max_area = 0;
        for (int i = 0; i < (int)heights.size(); ++i)
        {
            if (i > 0) {
                int dh = heights.at(i) - heights.at(i - 1);
                int right = heights.size() - i;
                if (dh - 1 < heights.at(i - 1) / right)
                    continue;
            }

            int win_min = heights.at(i);
            int win_sum = heights.at(i);
            for (int j = i; j < (int)heights.size(); ++j) {
                int bar = heights.at(j);
                int right = heights.size() - j;
                if (bar - 1 < (max_area - win_sum) / right)
                    break;

                win_min = std::min(win_min, bar);
                win_sum = win_min * (j - i + 1);
                max_area = std::max(max_area, win_sum);
            }
        }
        return max_area;
    }
};

}  /* namespace solution_084 */
